//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
//
// 示例 1: 
//
// 输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5
// 
//
// 示例 2: 
//
// 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
//输出: 4 
//
// 说明: 
//
// 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 
// 👍 1158 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class KthLargestElementInAnArray {
    public static void main(String[] args) {
        Solution solution = new KthLargestElementInAnArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        /***
         * 1. 快排
         * 2. 优先队列
         */
        public int findKthLargest(int[] nums, int k) {
            if (k>nums.length/2){
                quickSortFindKMin(nums,0,nums.length-1,nums.length-k);
                return nums[nums.length-k];
            }
            quickSortFindKMax(nums, 0, nums.length - 1, k-1);
            return nums[k - 1];
        }

        public int findKthLargestPriorQueue(int[] nums, int k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(k);
            for (int num : nums) {
                if (queue.size() < k || queue.peek() < num) {
                    queue.offer(num);
                }
                if (queue.size() > k) {
                    queue.poll();
                }
            }

            return queue.peek();
        }
        // 找第k小
        public void quickSortFindKMin(int[] nums, int l, int r, int k) {
            if (l >= r) {
                return;
            }
            int i = l;
            int j = r;
            while (i < j) {
                while (i < j && nums[l] <= nums[j]) {
                    j--;
                }
                while (i < j && nums[l] >= nums[i]) {
                    i++;
                }
                swap(nums, i, j);
            }
            swap(nums, i, l);
            if (i < k) {
                quickSortFindKMin(nums, i + 1, r, k);
            }
            if (i > k) {
                quickSortFindKMin(nums, l, i - 1, k);
            }

        }
        // 找第k大
        public void quickSortFindKMax(int[] nums, int l, int r, int k) {
            if (l >= r) {
                return;
            }
            int i = l;
            int j = r;
            while (i < j) {
                while (i < j && nums[l] >= nums[j]) {
                    j--;
                }
                while (i < j && nums[l] <= nums[i]) {
                    i++;
                }
                swap(nums, i, j);
            }
            swap(nums, i, l);
            if (i < k) {
                quickSortFindKMax(nums, i + 1, r, k);
            }
            if (i > k) {
                quickSortFindKMax(nums, l, i - 1, k);
            }

        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

